import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/24 16:21
 * @description 贪心 + TreeMap中 higher
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int[] avoidFlood(int[] rains) {
        int[] ans = new int[rains.length];
        Arrays.fill(ans, -1);
        Map<Integer, Integer> water = new HashMap<>();
        TreeSet<Integer> zero = new TreeSet<>();
        for(int i = 0; i < rains.length; ++i){
            int rain = rains[i];
            if(rain == 0){
                //晴天，存下标
                zero.add(i);
                continue;
            }
            //下雨天，且这个湖泊已经下过雨了
            if(water.containsKey(rain)){
                //找到之前一次下雨的下标所对应的下一个晴天下标，如果没有满足要求的晴天下标，返回空数组
                Integer r = zero.higher(water.get(rain));
                if(r == null) {
                    return new int[]{};
                }
                //清空的湖泊下标
                ans[r] = rain;
                zero.remove(r);
            }
            //存放下雨的湖泊
            water.put(rain, i);
        }
        // 剩下的晴天可以不抽干湖泊，返回1
        for (int i : zero) {
            ans[i] = 1;
        }
        return ans;
    }
}
